HTMLify
Smallest number on left.java
Views: 1 | Author: cody
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | import java.io.*; import java.util.*; import java.lang.*; class GFG{ public static void main(String args[])throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(in.readLine()); while(t-- > 0){ int n = Integer.parseInt(in.readLine()); String a1[] = in.readLine().trim().split("\\s+"); int a[] = new int[n]; for(int i = 0;i < n;i++) a[i] = Integer.parseInt(a1[i]); Solution ob = new Solution(); List<Integer> ans = new ArrayList<Integer>(); ans = ob.leftSmaller(n, a); for(int i = 0;i < n;i++) System.out.print(ans.get(i)+" "); System.out.println(); } } } // } Driver Code Ends //User function Template for Java class Solution{ static List<Integer> leftSmaller(int n, int a[]) { //code here List<Integer> a1=new LinkedList<>(); int[] ans=new int[n]; Arrays.fill(ans,-1); Stack<Integer> st=new Stack<>(); for(int i=n-1 ; i>=0;i--){ while(st.size()>0 && a[i]<a[st.peek()]){ int tbs=st.pop(); ans[tbs]=a[i]; } st.push(i); } for(int i=0;i<n;i++){ a1.add(ans[i]); } return a1; } } |